#include "Iterator.h"
using namespace std;

template<typename T>
struct Node {
    T data;
    Node* prev;
    Node* next;
    
    explicit Node(const T& value = T()) : data(value), prev(nullptr), next(nullptr) {}
};

template<typename T>
class DequeIterator : public iterator<
    bidirectional_iterator_tag,
    T,
    ptrdiff_t,
    T*,
    T&
> {
private:
    Node<T>* current;//指向双向队列的指针

public:
    //构造函数
    explicit DequeIterator(Node<T>* node = nullptr) : current(node) {};

    // 解引用操作符
    T& operator*() const { 
        if (!current) throw std::runtime_error("Dereferencing null iterator");
        return current->data; 
    }

    T* operator->() const { 
        if (!current) throw std::runtime_error("Dereferencing null iterator");
        return &current->data; 
    }

    //递增/递减操作符
    DequeIterator& operator++() {
        if (!current) throw std::runtime_error("Dereferencing null iterator");
        current = current->next;
        return *this;
    }

    DequeIterator operator++(int) {
        DequeIterator temp = *this;
        ++(*this);
        return temp;
    }

    DequeIterator& operator--() {
        if (!current) throw std::runtime_error("Dereferencing null iterator");
        current = current->prev;
        return *this;
    }

    DequeIterator operator--(int) {
        DequeIterator temp = *this;
        --(*this);
        return temp;
    }

    // 比较操作符
    bool operator==(const DequeIterator& other) const {
        return current == other.current;
    }
    
    bool operator!=(const DequeIterator& other) const {
        return !(*this == other);
    }
};

template<typename T, typename Allocator = std::allocator<T>>
class Deque {
private:
    using AllocTraits = std::allocator_traits<Allocator>;
    //rebind的意义是使类型T和类型Node<T>使用同一种分配方法
    using NodeAllocator = typename AllocTraits::template rebind_alloc<Node<T>>;
    using NodeTraits = std::allocator_traits<NodeAllocator>;

    Node<T>* head;       // 头节点指针
    Node<T>* tail;       // 尾节点指针
    size_t size_;        // 元素数量
    NodeAllocator alloc; // 内存分配器

public:
    // 类型定义
    using value_type = T;
    using reference = T&;
    using const_reference = const T&;
    using iterator = DequeIterator<T>;
    using const_iterator = DequeIterator<const T>;
    using size_type = size_t;

    // 构造函数
    Deque() : head(nullptr), tail(nullptr), size_(0) {}

    // 析构函数
    ~Deque() {
        clear();
    }

    // 迭代器接口
    iterator begin() { return iterator(head); }
    iterator end() { return iterator(nullptr); }
    const_iterator begin() const { 
        return const_iterator(const_cast<Node<T>*>(head)); 
    }
    const_iterator end() const { return const_iterator(nullptr); }
    const_iterator cbegin() const { return begin(); }
    const_iterator cend() const { return end(); }

    // 容量接口
    size_type size() const { return size_; }
    bool empty() const { return size_ == 0; }

    // 元素访问
    reference front() {
        if (empty()) throw std::out_of_range("Deque is empty");
        return head->data;
    }

    const_reference front() const {
        if (empty()) throw std::out_of_range("Deque is empty");
        return head->data;
    }

    reference back() {
        if (empty()) throw std::out_of_range("Deque is empty");
        return tail->data;
    }

    const_reference back() const {
        if (empty()) throw std::out_of_range("Deque is empty");
        return tail->data;
    }

    // 修改器 - 头部操作
    void push_front(const T& value) {
        Node<T>* newNode = NodeTraits::allocate(alloc, 1);
        NodeTraits::construct(alloc, newNode, value);

        if (!head) {
            head = tail = newNode;
        } else {
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
        size_++;
    }

    void pop_front() {
        if (empty()) return;

        Node<T>* oldHead = head;
        head = head->next;

        if (head) {
            head->prev = nullptr;
        } else {
            tail = nullptr; // 队列为空时更新尾指针
        }

        NodeTraits::destroy(alloc, oldHead);
        NodeTraits::deallocate(alloc, oldHead, 1);
        size_--;
    }

    // 修改器 - 尾部操作
    void push_back(const T& value) {
        Node<T>* newNode = NodeTraits::allocate(alloc, 1);
        NodeTraits::construct(alloc, newNode, value);

        if (!tail) {
            head = tail = newNode;
        } else {
            newNode->prev = tail;
            tail->next = newNode;
            tail = newNode;
        }
        size_++;
    }

    void pop_back() {
        if (empty()) return;

        Node<T>* oldTail = tail;
        tail = tail->prev;

        if (tail) {
            tail->next = nullptr;
        } else {
            head = nullptr; // 队列为空时更新头指针
        }

        NodeTraits::destroy(alloc, oldTail);
        NodeTraits::deallocate(alloc, oldTail, 1);
        size_--;
    }

    // 清空队列
    void clear() {
        while (head) {
            Node<T>* next = head->next;
            NodeTraits::destroy(alloc, head);
            NodeTraits::deallocate(alloc, head, 1);
            head = next;
        }
        tail = nullptr;
        size_ = 0;
    }
};

// 使用示例
int main() {
    Deque<int> deque;

    // 尾部添加元素
    deque.push_back(10);
    deque.push_back(20);
    deque.push_back(30);

    // 头部添加元素
    deque.push_front(5);
    deque.push_front(0);

    // 输出所有元素
    std::cout << "Deque contents (forward): ";
    for (auto it = deque.begin(); it != deque.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 访问首尾元素
    std::cout << "Front: " << deque.front() << ", Back: " << deque.back() << std::endl;

    // 删除元素
    deque.pop_front();
    deque.pop_back();

    // 范围for循环测试
    std::cout << "After pop: ";
    for (const auto& val : deque) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}    